Phó tế Kiều Công Tùng được truyền chức linh mục ngày 30 tháng 6 năm 1999 tại Nhà thờ Đức Bà Sài Gòn, bởi Tổng giám mục Gioan Baotixita Phạm Minh Mẫn, trở thành linh mục thuộc linh mục đoàn Tổng Giáo phận Thành phố Hồ Chí Minh. Ông sau đó được bổ nhiệm làm linh mục phụ tá Giáo xứ Bùi Phát thuộc Tổng giáo phận này.[3]

Rời xứ Bùi Phát, linh mục Kiều Công Tùng thực hiện mục vụ với tư cách trợ lý giáo sư chủng viện (Docente assistente)[11] tại Đại chủng viện Thánh Giuse Sài Gòn trong thời gian ngắn từ năm 2003 đến nămn 2004[gc 2], trước khi ông du học Hoa Kỳ tại Boston College và Boston University cho đến năm 2009. Trong suốt thời kỳ du học, ông tốt nghiệp Thạc sĩ Khoa học Xã hội (Master of Arts, M.A.), Thạc sĩ Mục vụ Thánh nhạc (Boston College) và Thạc sĩ Thần học chuyên ngành Phụng Tự (Boston University).[11][13] Hoàn tất việc du học và trở về Việt Nam, ông được bổ nhiệm làm linh mục phụ tá Nhà thờ chính tòa Đức Bà, và đảm nhận chức vụ này trong thời gian ngắn từ năm 2009 đến năm 2010.[3]

Từ năm 2010, linh mục Kiều Công Tùng tham gia giảng dạy tại Đại chủng viện Thánh Giuse Sài Gòn. Trong thời gian đó, giai đoạn từ năm 2010 đến năm 2016, ông là linh mục nội trú Đại chủng viện. Ngoài giảng dạy tại Đại chủng viện này, ông còn tham gia giảng dạy tại Học viện Công giáo Việt Nam và một số các học viện, dòng tu khác nhau. Từ năm 2016, ông kiêm nhiệm chức Chưởng ấn Tòa Tổng giám mục Tổng giáo phận Thành phố Hồ Chí Minh.[3] Trả lời phỏng vấn báo Giác Ngộ vào tháng 3 năm 2019 về vụ việc liên quan đến linh mục Giuse Trần Đình Long, linh mục Chưởng ấn Kiều Công Tùng cho rằng tình hình ngoài tầm kiểm soát của Tòa Tổng giám mục. Ông nhận định linh mục Long lạm dụng, trái quy định khi cử hành thánh lễ Công giáo, và lưu ý rằng Nhà nước phản ánh việc làm của linh mục Long là trái pháp luật. Linh mục Tùng khẳng định việc thu hút người ta đến bằng cách đặt tay để chữa bệnh, Giáo hội Công giáo không chủ trương việc đó.[14]

Ông từng là thuyết trình viên cho đề tài Bí tích Thánh Thể trong dịp tĩnh tâm linh mục đoàn Giáo phận Phát Diệm vào tháng 5 năm 2021.[15] Đây là lần đầu tiên ông hỗ trợ thường huấn cho các linh mục.[7] Trong nhiệm kỳ 2022 đến 2027, linh mục Kiều Công Tùng là thành viên Ban Tư Vấn, Hội đồng Linh mục và Hội đồng Mục vụ Tổng giáo phận Thành phố Hồ Chí Minh, theo thông báo sau dịp tĩnh tâm linh mục đoàn Tổng giáo phận vào tháng 11 năm 2022.[16] Ngoài vai trò Chưởng ấn (Thư ký Giám mục), linh mục Kiều Công Tùng còn kiêm nhiệm chức vụ Chưởng nghi của Tổng giáo phận Thành phố Hồ Chí Minh. Chức vụ Chưởng nghi đảm nhận các công tác về phụng tự và nghi lễ. Ông cũng là vị quản lý Quỹ Loan báo Tin Mừng, một quỹ đã được lập thời Tổng giám mục Phaolô Bùi Văn Đọc để mua các mảnh đất vùng ven và thiết lập các giáo điểm truyền giáo. Nguồn thu của quỹ này, ngoài quyên góp, còn có vay mượn.[7]